Bản vẽ tổng thể: Dạng chuẩn
Bài toán tối ưu hóa toán học, hay đơn giản là bài toán tối ưu hóa, có dạng tối thiểu hóa $f_0(x)$ với điều kiện $f_i(x) \le b_i$, với $i=1, \dots, m$. Về mặt hình thức, chúng ta biểu diễn điều này như sau:
$$\begin{aligned} &\text{Tối thiểu hóa} && f_0(x) \\ &\text{với điều kiện} && f_i(x) \le b_i, \quad i=1, \dots, m \end{aligned}$$Cấu trúc này chính là "ADN" của tối ưu hóa. Mỗi ký hiệu đều đại diện cho một thành phần quan trọng trong thế giới thực:
- Các tay cầm ($x$): Vector $x = (x_1, \dots, x_n)$ là biến tối ưu hóa của bài toán. Những yếu tố này đại diện cho các quyết định cụ thể hoặc tham số mà chúng ta có thể kiểm soát — ví dụ như trọng lượng máy bay không người lái và công suất động cơ.
- Mục tiêu ($f_0$): Hàm số $f_0 : \mathbf{R}^n \to \mathbf{R}$ là hàm mục tiêu, nó đo lường "chi phí" hoặc "mất mát" mà chúng ta muốn tối thiểu hóa, ví dụ như lượng năng lượng tiêu thụ trên mỗi dặm.
- Các quy tắc ($f_i \le b_i$): Các hàm số $f_i : \mathbf{R}^n \to \mathbf{R}, i = 1, \dots, m$, là các hàm ràng buộc (dạng bất đẳng thức), trong khi các hằng số $b_1, \dots, b_m$ là các giới hạn, hay biên, cho các ràng buộc. Những yếu tố này xác định không gian "khả thi" — máy bay không người lái phải tạo ra đủ lực nâng để bay và không được vượt quá giới hạn trọng lượng pin $b_i$.
Cuộc tìm kiếm giải pháp tối ưu
Tính tuyến tính so với tính phi tuyến
Độ phức tạp trong việc tìm ra $x^\star$ phụ thuộc hoàn toàn vào bản chất toán học của $f_0$ và $f_i$.
Nếu bài toán tối ưu hóa không phải là tuyến tính (tức là thiếu tính tỷ lệ và tính cộng tính), thì nó được gọi là một chương trình phi tuyến. Các chương trình phi tuyến là vùng đất hoang dã trong lĩnh vực tối ưu hóa; chúng thiếu cấu trúc dự đoán được như các hệ thống tuyến tính và đòi hỏi một bộ công cụ phân tích hoàn toàn khác biệt, thường phức tạp hơn nhiều để giải quyết.